package com.Oct_SevenTeen;

import java.util.ArrayList;
import java.util.List;

/**
 * 653. 两数之和 IV - 输入二叉搜索树
 * 给定一个二叉搜索树 root 和一个目标结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true。
 *
 *
 *
 * 2022/10/18 00:21
 */

public class Solution653 {

    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list=new ArrayList<>();
        dfs(root,list);
        int left=0,right=list.size()-1;
        while (left<right)
        {
            int sum=list.get(left)+list.get(right);
            if (sum==k) return true;
            else if (sum<k)
            {
                left++;
            }else
            {
                right--;
            }
        }
        return false;
    }

    void dfs(TreeNode root, List<Integer> list){
        if (root!=null)
        {
            dfs(root.left,list);
            list.add(root.val);
            dfs(root.right,list);
        }
    }


    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

}
